home *** CD-ROM | disk | FTP | other *** search
/ Shareware Grab Bag / Shareware Grab Bag.iso / 020 / arcsourc.arc / ARCLZW.MAC < prev    next >
Encoding:
Text File  |  1985-07-02  |  15.5 KB  |  414 lines
  1. /*  ARC - Archive utility - ARCLZW
  2.  
  3. $define(tag,$$segment(@1,$$index(@1,=)+1))#
  4. $define(version,Version $tag(
  5. TED_VERSION DB =1.39), created on $tag(
  6. TED_DATE DB =07/02/85) at $tag(
  7. TED_TIME DB =10:36:00))#
  8. $undefine(tag)#
  9.     $version
  10.  
  11. (C) COPYRIGHT 1985 by System Enhancement Associates; ALL RIGHTS RESERVED
  12.  
  13.     By:  Thom Henderson
  14.  
  15.     Description:
  16.          This file contains the routines used to implement Lempel-Zev
  17.          data compression, which calls for building a coding table on
  18.          the fly.  This form of compression is especially good for encoding
  19.          files which contain repeated strings, and can often give dramatic
  20.          improvements over traditional Huffman SQueezing.
  21.  
  22.     Language:
  23.          Computer Innovations Optimizing C86
  24.  
  25.     Programming notes:
  26.          In this section I am drawing heavily on the LZWCOM and LZWUNC
  27.          programs by Kent Williams of Cedar Rapids Iowa.  This section
  28.          is mainly his code, and I don't pretend to understand everything
  29.          that's going on, so please refer any technical questions to him.
  30.  
  31.          As best as I can tell, this method works by tracing down a hash
  32.          table of code strings where each entry has the property:
  33.  
  34.               if <string> <char> is in the table
  35.               then <string> is in the table.
  36. */
  37. #include <stdio.h>
  38.  
  39. long lzwlen;                           /* length after crunching */
  40.  
  41. #define FALSE    0
  42. #define TRUE     !FALSE
  43. #define TABSIZE  4096
  44. #define NO_PRED  0xFFFF
  45. #define EMPTY    0xFFFF
  46. #define NOT_FND  0xFFFF
  47.  
  48. static unsigned int inbuf;             /* partial input code storage */
  49. static unsigned int outbuf;            /* partial output code storage */
  50.  
  51. static unsigned char stack[TABSIZE];   /* local push and pop stack */
  52. static int sp;                         /* current stack pointer */
  53.  
  54. static struct entry                    /* string table entry format */
  55. {   char used;                         /* true when this entry is in use */
  56.     unsigned int next;                 /* ptr to next in collision list */
  57.     unsigned int predecessor;          /* code for preceeding string */
  58.     unsigned char follower;            /* char following string */
  59. }   string_tab[TABSIZE];               /* the code string table */
  60.  
  61. /*  The h() routine is used to calculate a hash value, using the
  62.     "mid-square" algorithm.  That is, a primitive hash value is
  63.     calculated by taking the middle twelve bits of the square of a key.
  64. */
  65.  
  66. static unsigned h(pred,foll)           /* calculate basic hash value */
  67. unsigned int pred;                     /* code for preceeding string */
  68. unsigned char foll;                    /* value of following char */
  69. {
  70.     long local;                        /* local hash value */
  71.  
  72.     local = (pred + foll) | 0x0800;    /* create the hash key */
  73.     local *= local;                    /* square it */
  74.     return (local >> 6) & 0x0FFF;      /* return the middle 12 bits */
  75. }
  76.  
  77. /*  The eolist() function is used to trace down a list of entries with
  78.     duplicate keys until the last duplicate is found.
  79. */
  80.  
  81. static unsigned eolist(index)          /* find last duplicate */
  82. unsigned int index;
  83. {
  84.     int temp;
  85.  
  86.     while(temp=string_tab[index].next) /* while more duplicates */
  87.          index = temp;
  88.  
  89.     return index;
  90. }
  91.  
  92. /*  The hash() routine is used to find a spot in the hash table for a new
  93.     entry.  It performs a "hash and linear probe" lookup, using h() to
  94.     calculate the starting hash value and eolist() to perform the linear
  95.     probe.  This routine DOES NOT detect a table full condition.  That
  96.     MUST be checked for elsewhere.
  97. */
  98.  
  99. static unsigned hash(pred,foll)        /* find spot in the string table */
  100. unsigned int pred;                     /* code for preceeding string */
  101. unsigned char foll;                    /* char following string */
  102. {
  103.     unsigned int local, tempnext;      /* scratch storage */
  104.     struct entry *ep;                  /* allows faster table handling */
  105.  
  106.     local = h(pred,foll);              /* get initial hash value */
  107.  
  108.     if(!string_tab[local].used)        /* if that spot is free */
  109.          return local;                 /* then that's all we need */
  110.  
  111.     else                               /* else a collision has occured */
  112.     {    local = eolist(local);        /* move to last duplicate */
  113.  
  114.          /*   We must find an empty spot. We start looking 101 places
  115.               down the table from the last duplicate.
  116.          */
  117.  
  118.          tempnext = (local+101) & 0x0FFF;
  119.          ep = &string_tab[tempnext];   /* initialize pointer */
  120.  
  121.          while(ep->used)               /* while empty spot not found */
  122.          {    if(++tempnext==TABSIZE)  /* if we are at the end */
  123.               {    tempnext = 0;       /* wrap to beginning of table*/
  124.                    ep = string_tab;
  125.               }
  126.               else ++ep;               /* point to next element in table */
  127.          }
  128.  
  129.          /*   local still has the pointer to the last duplicate, while
  130.               tempnext has the pointer to the spot we found.  We use
  131.               this to maintain the chain of pointers to duplicates.
  132.          */
  133.  
  134.          string_tab[local].next = tempnext;
  135.  
  136.          return tempnext;
  137.     }
  138. }
  139.  
  140. /*  The unhash() function is used to search the hash table for a given key.
  141.     Like hash(), it performs a hash and linear probe search.  It returns
  142.     either the number of the entry (if found) or NOT_FND (if not found).
  143. */
  144.  
  145. static unsigned unhash(pred,foll)      /* search string table for a key */
  146. unsigned int pred;                     /* code of preceeding string */
  147. unsigned char foll;                    /* character following string */
  148. {
  149.     unsigned int local, offset;        /* scratch storage */
  150.     struct entry *ep;                  /* this speeds up access */
  151.  
  152.     local = h(pred,foll);              /* initial hash */
  153.  
  154.     while(1)
  155.     {    ep = &string_tab[local];      /* speed up table access */
  156.  
  157.          if((ep->predecessor==pred) && (ep->follower==foll))
  158.               return local;            /* we have a match */
  159.  
  160.          if(!ep->next)                 /* if no more duplicates */
  161.               return NOT_FND;          /* then key is not listed */
  162.  
  163.          local = ep->next;             /* move on to next duplicate */
  164.     }
  165. }
  166.  
  167. /*  The init_tab() routine is used to initialize our hash table.
  168.     You realize, of course, that "initialize" is a complete misnomer.
  169. */
  170.  
  171. static init_tab()                      /* set ground state in hash table */
  172. {
  173.     unsigned int i;                    /* table index */
  174.  
  175.     setmem((char *)string_tab,sizeof(string_tab),0);
  176.  
  177.     for(i=0; i<256; i++)               /* list all single byte strings */
  178.          upd_tab(NO_PRED,i);
  179.  
  180.     inbuf = outbuf = EMPTY;            /* nothing is in our buffers */
  181. }
  182.  
  183. /*  The upd_tab routine is used to add a new entry to the string table.
  184.     As previously stated, no checks are made to ensure that the table
  185.     has any room.  This must be done elsewhere.
  186. */
  187.  
  188. upd_tab(pred,foll)                     /* add an entry to the table */
  189. unsigned int pred;                     /* code for preceeding string */
  190. unsigned int foll;                     /* character which follows string */
  191. {
  192.     struct entry *ep;                  /* pointer to current entry */
  193.  
  194.     /* calculate offset just once */
  195.  
  196.     ep = &string_tab[hash(pred,foll)];
  197.  
  198.     ep->used = TRUE;                   /* this spot is now in use */
  199.     ep->next = 0;                      /* no duplicates after this yet */
  200.     ep->predecessor = pred;            /* note code of preceeding string */
  201.     ep->follower = foll;               /* note char after string */
  202. }
  203.  
  204. /*  This algorithm encodes a file into twelve bit strings (three nybbles).
  205.     The getcode() and putcode() routines are used to output these strings
  206.     a byte (or two) at a time.
  207. */
  208.  
  209. static getcode(fd)                     /* read in a twelve bit code */
  210. FILE *fd;                              /* file to get code from */
  211. {
  212.     unsigned int localbuf, returnval;
  213.  
  214.     if(inbuf==EMPTY)                   /* if on a code boundary */
  215.     {    if((localbuf=getc_unp(fd))==EOF)   /* get start of next code */
  216.               return EOF;              /* pass back end of file status */
  217.          localbuf &= 0xFF;             /* mask down to true byte value */
  218.          if((inbuf=getc_unp(fd))==EOF) /* get end of code, start of next */
  219.               return EOF;              /* this should never happen */
  220.          inbuf &= 0xFF;                /* mask down to true byte value */
  221.  
  222.          returnval = ((localbuf<<4)&0xFF0) + ((inbuf>>4)&0x00F);
  223.          inbuf &= 0x000F;              /* leave partial code pending */
  224.     }
  225.  
  226.     else                               /* buffer contains first nybble */
  227.     {    if((localbuf=getc_unp(fd))==EOF)
  228.               return EOF;
  229.          localbuf &= 0xFF;
  230.  
  231.          returnval = localbuf + ((inbuf<<8)&0xF00);
  232.          inbuf = EMPTY;                /* note no hanging nybbles */
  233.     }
  234.     return returnval;                  /* pass back assembled code */
  235. }
  236.  
  237. static putcode(fd,code)                /* output a twelve bit code */
  238. FILE *fd;                              /* file to send code to */
  239. unsigned int code;                     /* code to send */
  240. {
  241.     int localbuf;
  242.  
  243.     if(outbuf==EMPTY)                  /* if no hanging nybbles */
  244.     {    putch(((code>>4)&0xFF),fd);   /* then output first two nybbles */
  245.          outbuf = code & 0x000F;       /* and save third for later */
  246.     }
  247.     else                               /* else dump pending nybble */
  248.     {    putch((((outbuf<<4)&0xFF0) + ((code>>8)&0x00F)),fd);
  249.          putch((code&0x00FF),fd);      /* last two nybbles can go also */
  250.          outbuf = EMPTY;               /* and no nybbles left hanging */
  251.     }
  252. }
  253.  
  254. /*  The putch() routine is used to write bytes to the output file,
  255.     as certain checks must be performed.
  256. */
  257.  
  258. static putch(c,fp)                     /* output a byte value */
  259. char c;                                /* the byte value to put */
  260. FILE *fp;                              /* the file to output to */
  261. {
  262.     lzwlen++;                          /* bump our length counter */
  263.  
  264.     if(fp)                             /* if output file is real */
  265.          if(fputc(c,fp)==EOF)          /* then make sure this works */
  266.               abort("Write fail (disk full?)");
  267. }
  268.  
  269. /*  The flushout() routine must be called to flush out any partial code
  270.     which gets left behind.
  271. */
  272.  
  273. static flushout(fd)                    /* flush out the final code */
  274. FILE *fd;                              /* file to send code to */
  275. {
  276.     if(outbuf!=EMPTY)                  /* dump any hanging nybble */
  277.          putch(((outbuf<<4)&0xFF0),fd);
  278. }
  279.  
  280. static push(c)                         /* push char onto stack */
  281. int c;                                 /* character to push */
  282. {
  283.     stack[sp] = ((char) c);            /* coerce integer into a char */
  284.  
  285.     if(++sp >= TABSIZE)
  286.          abort("Stack overflow\n");
  287. }
  288.  
  289. static int pop()                       /* pop character from stack */
  290. {
  291.     if(sp>0)
  292.          return ((int) stack[--sp]);   /* leave ptr at next empty slot */
  293.  
  294.     else return EMPTY;
  295. }
  296.  
  297. /***** LEMPEL-ZEV DECOMPRESSION *****/
  298.  
  299. static int code_count;                 /* needed to detect table full */
  300. static unsigned code;                  /* where we are so far */
  301. static int firstc;                     /* true only on first character */
  302.  
  303. init_ucr()                             /* get set for uncrunching */
  304. {
  305.     sp = 0;                            /* clear out the stack */
  306.     init_tab();                        /* set up atomic code definitions */
  307.     code_count = TABSIZE - 256;        /* note space left in table */
  308.     firstc = 1;                        /* true only on first code */
  309. }
  310.  
  311. int getc_ucr(f)                        /* get next uncrunched byte */
  312. FILE *f;                               /* file containing crunched data */
  313. {
  314.     unsigned int c;                    /* a character of input */
  315.     int code, newcode;
  316.     static int oldcode, finchar;
  317.     struct entry *ep;                  /* allows faster table handling */
  318.  
  319.     if(firstc)                         /* first code is always known */
  320.     {    firstc = FALSE;               /* but next will not be first */
  321.          oldcode = getcode(f);
  322.          return finchar = string_tab[oldcode].follower;
  323.     }
  324.  
  325.     if(!sp)                            /* if stack is empty */
  326.     {    if((code=newcode=getcode(f))==EOF)
  327.               return EOF;
  328.  
  329.          ep = &string_tab[code];       /* initialize pointer */
  330.  
  331.          if(!ep->used)                 /* if code isn't known */
  332.          {    code = oldcode;
  333.               ep = &string_tab[code];  /* re-initialize pointer */
  334.               push(finchar);
  335.          }
  336.  
  337.          while(ep->predecessor!=NO_PRED)
  338.          {    push(ep->follower);      /* decode string backwards */
  339.               code = ep->predecessor;
  340.               ep = &string_tab[code];
  341.          }
  342.  
  343.          push(finchar=ep->follower);   /* save first character also */
  344.  
  345.          /*   The above loop will terminate, one way or another,
  346.               with string_tab[code].follower equal to the first
  347.               character in the string.
  348.          */
  349.  
  350.          if(code_count)                /* if room left in string table */
  351.          {    upd_tab(oldcode,finchar);
  352.               --code_count;
  353.          }
  354.  
  355.          oldcode = newcode;
  356.     }
  357.  
  358.     return pop();                      /* return saved character */
  359. }
  360.  
  361.  
  362. /***** LEMPEL-ZEV COMPRESSION *****/
  363.  
  364. init_cr()                              /* initialize for Lempel-Zev pack */
  365. {
  366.     init_tab();                        /* set string table ground state */
  367.     code_count = TABSIZE - 256;        /* set initial table space */
  368.     firstc = 1;                        /* set up special case */
  369.     lzwlen = 0;                        /* reset length counter */
  370. }
  371.  
  372. putc_cr(c,t)                           /* output a byte crunched */
  373. char c;                                /* character to crunch */
  374. FILE *t;                               /* file to write to */
  375. {
  376.     unsigned localcode;
  377.  
  378.     if(firstc)                         /* special case for first char */
  379.     {    code = unhash(NO_PRED,c);     /* set initial code for table */
  380.          firstc = 0;                   /* no longer first char */
  381.          return;
  382.     }
  383.  
  384.     if((localcode=unhash(code,c))!=NOT_FND)
  385.     {    code = localcode;
  386.          return;
  387.     }
  388.  
  389.     /*   When the above clause comes false, we have found the code for
  390.          the longest known code string.
  391.     */
  392.  
  393.     putcode(t,code);                   /* save code for string thus far */
  394.  
  395.     if(code_count)                     /* if more room in string table */
  396.     {    upd_tab(code,c);              /* then add the new string */
  397.          --code_count;
  398.     }
  399.  
  400.     /*   Now we start the loop again, starting with the character
  401.          that didn't fit in the last string.
  402.     */
  403.  
  404.     code = unhash(NO_PRED,c);
  405. }
  406.  
  407. fini_cr(t)                             /* finish up after crunching */
  408. FILE *t;                               /* file to dump to */
  409. {
  410.     putcode(t,code);                   /* always one unsent code left */
  411.  
  412.     flushout(t);                       /* make sure everything's written */
  413. }
  414.